import java.util.HashMap;
import java.util.Map;

public class Dpmaxsubarr {
	
	static class Maxtuple {
		int max;
		int start;
		int end;
	}
	private static Maxtuple[] maxs = new Maxtuple[8]; // 此处偷懒了
	
	// 重载getMaxSubArr函数，实现默认参数
	public static void getMaxSubArr(Integer[] arr, int end) {
		boolean isRecursion = false;
		getMaxSubArr(arr, end, isRecursion);
	}
	
	// 以end为结尾的最大子数组
	public static Map<String, Integer> getMaxSubArr(Integer[] arr, int end, boolean isRecursion) {
		Map<String, Integer> map = new HashMap<String, Integer>();
		if (maxs[end] != null) {
			map.put("maxV", maxs[end].max);
			map.put("start", maxs[end].start);
			map.put("end", maxs[end].end);
			return map;
		}
		if (end == 0) {
			map.put("maxV", arr[end]);
			map.put("start", end);
			map.put("end", end);
		} else {
			Map<String, Integer> preMax = getMaxSubArr(arr, end-1, true);
			if (isRecursion) {
				System.out.println("进入递归");
			}
			if (preMax.get("maxV") < 0) {
				map.put("maxV", arr[end]);
				map.put("start", end);
				map.put("end", end);
			} else {
				map.put("maxV", arr[end]+preMax.get("maxV"));
				map.put("start", preMax.get("start"));
				map.put("end", end);
			}
		}
		maxs[end] = new Maxtuple();
		maxs[end].max = map.get("maxV");
		maxs[end].start = map.get("start");
		maxs[end].end = map.get("end");
		return map;
	}
	
	public static void main(String[] args) {
		Integer[] arr = {1, 4, -3, 4, -2, 9, 2, -4};
		Map<String, Integer> max = new HashMap<String, Integer>();
		max.put("maxV", -65535);
		max.put("start", 0);
		max.put("end", 0);
		for (int i=0; i<arr.length; i++) {
			Map<String, Integer> current = getMaxSubArr(arr, i, false);
			if (current.get("maxV") > max.get("maxV")) {
				max.put("maxV", current.get("maxV"));
				max.put("start", current.get("start"));
				max.put("end", current.get("end"));
			}
		}
		for (int i = 0; i < arr.length; i++) {
			System.out.printf("-(%d)-", arr[i]);
		}
		System.out.printf("\nmax=%d, start=%d, end=%d", max.get("maxV"), max.get("start"), max.get("end"));
	}
	
}
